Approximation Algorithms for Hard Capacitated $k$-facility Location Problems

摘要

We study the capacitated $k$-facility location problem, in which we are givena set of clients with demands, a set of facilities with capacities and aconstant number $k$. It costs $f_i$ to open facility $i$, and $c_{ij}$ forfacility $i$ to serve one unit of demand from client $j$. The objective is toopen at most $k$ facilities serving all the demands and satisfying the capacityconstraints while minimizing the sum of service and opening costs. In this paper, we give the first fully polynomial time approximation scheme(FPTAS) for the single-sink (single-client) capacitated $k$-facility locationproblem. Then, we show that the capacitated $k$-facility location problem withuniform capacities is solvable in polynomial time if the number of clients isfixed by reducing it to a collection of transportation problems. Third, weanalyze the structure of extreme point solutions, and examine the efficiency ofthis structure in designing approximation algorithms for capacitated$k$-facility location problems. Finally, we extend our results to obtain animproved approximation algorithm for the capacitated facility location problemwith uniform opening cost.